package Java1Test;

import utils.PrintArr;

public class InsertionSort {
    public static void main(String[] args) {

        //无序数组
        int[] arr = {54, 26, 93, 17, 77, 31, 44, 55, 20, 88};

        //有序数组
//        int[] arr = {1, 2, 3};

        // 1. 找到无序子数组的起始索引
        // 初始化为-1，表示假设数组已经有序
        int startIndex = -1;
        // 遍历数组，寻找第一个逆序对（前一个元素 > 后一个元素）
        // 注意：i < arr.length - 1 防止访问越界
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // 找到逆序对，记录无序子数组的起始位置
                startIndex = i + 1;
                break;
            }
        }

        // 2. 处理数组已经有序的情况
        // 如果遍历完数组都没有找到逆序对，startIndex保持-1
        if (startIndex == -1) {
            System.out.println("数组已经有序");
            PrintArr.printArr(arr); // 直接打印数组
            return; // 提前结束程序
        }

        // 3. 对无序子数组执行插入排序
        // 从startIndex开始遍历每个元素，将其插入到前面已排序部分的正确位置
        for (int i = startIndex; i < arr.length; i++) {
            // 当前待插入的元素索引
            int j = i;

            // 向前比较，将当前元素交换到正确位置
            // j > 0 确保不会访问索引-1
            while (j > 0 && arr[j - 1] > arr[j]) {
                // 交换 arr[j-1] 和 arr[j]
                int tmp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = tmp;
                j--; // 继续向前比较
            }
        }

        // 4. 输出排序结果
        PrintArr.printArr(arr);
    }
}